package leetcode_800;

import java.util.Arrays;

/**
 *@author 周杨
 *FindKthSmallestPairDistance_719_ 给定一个数组 里面2个元素组成的结构成为pair 找出第k差值小的pair差值
 *describe:用二分搜索 很好的题目 跟找出一个数组里第k大的元素一样的思想 AC 41%
 *2018年10月12日 下午2:33:00
 */
public class FindKthSmallestPairDistance_719_ {
	public static void main(String[] args) {
		FindKthSmallestPairDistance_719_ test=new FindKthSmallestPairDistance_719_();
		System.out.println(test.smallestDistancePair1(new int[]
				{9,10,7,10,6,1,5,4,9,8},18));
	}
	
	private int upperBound(int[] a, int low, int high, int key) {
        if (a[high] <= key) return high + 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (key >= a[mid]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
    
    // Returns number of pairs with absolute difference less than or equal to mid.
    private int countPairs(int[] a, int mid) {
        int n = a.length, res = 0;
        for (int i = 0; i < n; i++) {
            res += upperBound(a, i, n - 1, a[i] + mid) - i - 1;
        }
        return res;
    }

    public int smallestDistancePair(int a[], int k) {
        int n = a.length;
        Arrays.sort(a);

        // Minimum absolute difference
        int low = a[1] - a[0];
        for (int i = 1; i < n - 1; i++)
            low = Math.min(low, a[i + 1] - a[i]);

        // Maximum absolute difference
        int high = a[n - 1] - a[0];

        // Do binary search for k-th absolute difference
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (countPairs(a, mid) < k)
                low = mid + 1;
            else
                high = mid;
        }

        return low;
    }
	
	
	/**
	 * describe:思想错误 企图将数组划分成能二分搜索的区域 其实并非Index距离小 就是差值小 如1 4 5 6 6 6
	 * 2018年10月12日 下午2:29:24
	 */
	public int smallestDistancePair1(int[] nums, int k) {
        Arrays.sort(nums);
        int index=1,size=nums.length-1;
        //那么此时有序的排列对间隔便是1<->nums.length-1
        while(k>size) {
        	k-=size;
        	size--;//减小规模
        	index++;
        }
        int sort[]=new int[nums.length-index];
        for(int i=0;i<nums.length-index;++i) {
        	sort[i]=nums[i+index]-nums[i];
        }
        return findKthLargest(sort, sort.length-k+1);
    }
	
	public int findKthLargest(int[] nums, int k) {
        if(nums==null || k>nums.length)
            return -1;
        return partitionHelper(nums, k, 0, nums.length-1);
    }
    private int partitionHelper(int[] nums, int k, int start, int end) {
        int mid = nums[(start+end)/2];//使数组左边全部大于这个中间数  数组右边全部小于这个中间数
        int left = start, right = end;
        while(left<=right) {
            while(left<=right && nums[left]>mid) {//保证左边那个数小于或者等于中间那个数
                left++;
            }
            while(left<=right && nums[right]<mid) {//保证右边那个数大于中间那个数
                right--;
            }
            if(left<=right) {
                int temp = nums[left];
                nums[left++] = nums[right];
                nums[right--] = temp;
            }
        }

        if(right - start +1 >= k)
            return partitionHelper(nums, k, start, right);
        if(left - start < k)
            return partitionHelper(nums, k-(left-start), left, end);
        return nums[right+1];
        
    }
}
